public class Solution1473 {
    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        int[][][] f=new int[m+1][n+1][target+1];
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                for (int k=0;k<=target;k++){
                    f[i][j][k]=Integer.MAX_VALUE/2;
                }
            }
        }
        if (houses[0]==0){
            for (int j=0;j<n;j++){
                f[0][j][1]=cost[0][j];
            }
        }else{
            f[0][houses[0]-1][1]=0;
        }
        for (int i=1;i<m;i++){
            if (houses[i]==0){
                for (int j=0;j<n;j++){
                    for (int k=1;k<=Math.min(target,i+1);k++){
                        f[i][j][k]=Math.min(f[i][j][k],f[i-1][j][k]+cost[i][j]);
                        for (int p=0;p<n;p++){
                            if (p!=j){
                                f[i][j][k]=Math.min(f[i][j][k],f[i-1][p][k-1]+cost[i][j]);
                            }
                        }
                    }
                }
            }else{
                for (int k=1;k<=Math.min(target,i+1);k++){
                    f[i][houses[i]-1][k]=Math.min(f[i][houses[i]-1][k],f[i-1][houses[i]-1][k]);
                    for (int p=0;p<n;p++){
                        if (p!=houses[i]-1){
                            f[i][houses[i]-1][k]=Math.min(f[i][houses[i]-1][k],f[i-1][p][k-1]);
                        }
                    }
                }
            }
        }
        int ans=Integer.MAX_VALUE;
        for (int j=0;j<n;j++){
            ans=Math.min(ans,f[m-1][j][target]);
        }
        return ans==Integer.MAX_VALUE/2?-1:ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1473().minCost(new int[]{2,3,0},new int[][]{{5,2,3},{3,4,1},{1,2,1}},3,3,3));
    }
}
